package com.zp.self.module.level_4_算法练习.数学.数学推理;

/**
 * @author By ZengPeng
 */
public class 力扣_43_字符串相乘 {
    //测试
    public static void main(String[] args) {
//        String multiply = new 力扣_43_字符串相乘().
//                multiply("12311111111111111111111111111111111111111111111143223", "456111111111111111111111111111111111111111111321231");
//        System.out.println(multiply);
        System.out.println(new 力扣_43_字符串相乘().multiply("9133","0"));
//        System.out.println(new 力扣_43_字符串相乘().multiply("99","99"));
    }

    /**
    题目：给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，
     它们的乘积也表示为字符串形式。
     注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

     示例 1:
     输入: num1 = "2", num2 = "3"
     输出: "6"

     示例 2:
     输入: num1 = "123", num2 = "456"
     输出: "56088"

     提示：
     1 <= num1.length, num2.length <= 200
     num1 和 num2 只能由数字组成。
     num1 和 num2 都不包含任何前导零，除了数字0本身。

    分析：【perfect】
       1.分成个位与个位相乘：记录进位，
            遍历；从后向前。拆分num1单个字符逐个【乘以】num2的字符
            字符相乘，字符相加，
            都在100以内的计算，不会溢出
       大神解法：数组存储相乘的值, arr[i+j+1] += num1[i] * num2[j]
                n位 * m位 = [n+m,n+m-1,0] 这3中可能
            【还是有溢出的风险啊,但几乎不可能，要上面的数长度>8千万，一般不会】

    边界值 & 注意点：
       1.某个值为0
     **/
    //大神解法
    public String multiply(String num1, String  num2) {
        char[] n1 = num1.toCharArray();
        char[] n2 = num2.toCharArray();
        int len=n1.length+n2.length;
        int[] arr = new int[len];
        //给数组填充数据
        for (int i = n1.length-1; i>=0; i--) {
            for (int j = n2.length-1; j>=0; j--)
                arr[j+i+1] += (n1[i]-'0')*(n2[j]-'0');
        }
        //数组中从后向前进位
        for (int i = arr.length-1; i >0; i--) {
            arr[i-1] +=arr[i]/10;
            arr[i] = arr[i]%10;
        }
        //判断第一位是否是0，除0.第二位任然是0，那就返回0
        int index =0;
        if(arr[0]==0){
            if(arr[1]==0)return "0";
            else index++;
        }
        //数组构建字符串
        StringBuilder sb= new StringBuilder();
        while (index<len)
            sb.append(arr[index++]);
        return sb.toString();
    }

    //1.分成个位与个位相乘：记录进位，
    public String multiply2(String num1, String num2) {
        String sum="0";
        int index=0;//当前成绩应乘10的多少倍，即使添加多少个0
        for (int i = num1.length()-1; i >=0 ; i--) {
            int current =num1.charAt(i)-'0';
            if(current==0){
                index++;continue;
            }
            String sumPart = multiplyPart(current,num2,index);
//            System.out.print("当前和:"+sumPart);
            sum = add(sum,sumPart);
//            System.out.println("，总和:"+sum);
            index++;
        }
        return sum;
    }

    /**
    *  current * num2  ，然后加上sum
    * @ current   当前位数字
    * @ num2  字符串2
    * @ index  当前位数字 是多少位，相应要乘以多少个10
    * @ sum  当前的和
    **/
    private String multiplyPart(int current, String num2, int index) {
        if(num2.equals("0"))return "0";
        int carry=0;//进位
        StringBuilder sumPart = new StringBuilder();
        for (int i = num2.length()-1; i>=0; i--) {
            int num = current*(num2.charAt(i)-'0')+carry;
            carry= num/10;
            sumPart.append(num%10);
        }
        if(carry!=0)sumPart.append(carry);
        sumPart.reverse();
        while (index>0){
            sumPart.append("0");
            index--;
        }
        return sumPart.toString();
    }

    /**
     * 两个字符串类型的数字相加
     * @param  sum   当前和
     * @param sumPart  部分和
     **/
    private String add(String sum, String sumPart) {
        StringBuilder sb= new StringBuilder();
        int sumIndex = sum.length()-1;
        int partIndex = sumPart.length()-1;
        int carry=0;//进位
        while (sumIndex>=0 || partIndex>=0 || carry>0){
            int numb =carry;
            if(sumIndex>=0) numb += sum.charAt(sumIndex)-'0';
            if(partIndex>=0) numb += (sumPart.charAt(partIndex)-'0');
            carry=numb>=10?1:0;
            sb.append(numb>=10?numb-10:numb);
            sumIndex--;partIndex--;
        }
        return sb.reverse().toString();
    }

}
